(define (error m e)
  (begin
    (display m)
    (display e)
    (newline)))

(define (interpret t c)
  (if (null? t)
      c
      (interpret (cdr t) (interpret-step (car t) c))))

(define builtins
  (cons (cons '+ +)
	(cons (cons '- -)
	      (cons (cons '* *)
		    (cons (cons '/ /)
			  (cons (cons 'mod modulo)
				'()))))))

(define assoc assq)

(define (interpret-arith t c)
  (if (number? t)
      t
      (if (symbol? t)
	  (let* ((v (assoc t (car c))))
	    (if v
		(cdr v)
		(error "Variable lookup error in arith: " t)))
	  (if (pair? t)
	      (let* ((o (assoc (car t) builtins)))
		(if o
		    (let* ((l (interpret-arith (car (cdr t)) c))
			  (r (interpret-arith (car (cdr (cdr t))) c)))
		      ((cdr o) l r))
		    (error "Not a builtin: " (car t))))
	      (error "Invalid arithmetic expression: " t)))))

(define (interpret-bool t c)
  (if (pair? t)
      (if (eq? (car t) 'not)
	  (not (interpret-bool (car (cdr t)) c))
	  (if (eq? (car t) '=)
	      (= (interpret-arith (car (cdr t)) c) (interpret-arith (car (cdr (cdr t))) c))
	      (if (eq? (car t) '<)
		  (< (interpret-arith (car (cdr t)) c) (interpret-arith (car (cdr (cdr t))) c))
		  (if (eq? (car t) 'and)
		      (interpret-bool (cadr t) (caddr t))
		      (if (eq? (car t) 'or)
			  (interpret-bool (cadr t) (caddr t))
			  (error "Invalid boolean expression: " t))))))
      (if (eq? t 'true)
	  #t
	  (if (eq? t 'false)
	      #f
	      (if (symbol? t)
		  (let* ((v (assoc t (car c))))
		    (if v
			(interpret-bool (cdr v) c)
			(error "Variable lookup error in bool: " t)))
		  (error "Invalid boolean expression: " t))))))

; t = (assign a b) | (skip) | ...
; return = (assignments, output)
(define (interpret-step t c)
  (let* ((i (car t)))
    (if (eq? 'assign i)
	(let* ((id (car (cdr t)))
	      (val (interpret-arith (car (cdr (cdr t))) c)))
	  (cons (cons (cons id val) (car c)) (cdr c)))
	(if (eq? 'skip i)
	    c
	    (if (eq? 'out i)
		(let* ((val (cdr (assoc (car (cdr t)) (car c)))))
		  (cons (car c) (cons val (cdr c))))
		(if (eq? 'if i)
		    (let* ((cn (interpret-bool (car (cdr t)) c))
			  (tr (car (cdr (cdr t))))
			  (fa (car (cdr (cdr (cdr t))))))
		      (if cn
			  (interpret tr c)
			  (interpret fa c)))
		    (if (eq? 'while i)
			(let* ((cn (car (cdr t)))
			      (bd (car (cdr (cdr t)))))
			  (if (interpret-bool cn c)
			      (interpret-step t (interpret bd c))
			      c))
			(error "Error in step:" t))))))))

; supposedly prints out first 100 primes
(define primes '((assign p 0)
		 (assign n 2)
		 
		 (while (not (= p 100))
			((assign d 2)
			 (assign t 0)
			
			 (while (< d n)
				((if (= (mod n d) 0)
				     ((assign d n)
				      (assign t 1))
				     ((assign d (+ d 1))))))
				
			 (if (= t 0)
			     ((assign p (+ p 1))
			      (out n))
			     ((skip)))
			 
			 (assign n (+ n 1))))))
			   

;(display (interpret '((assign a 1) (skip) (assign b 2) (assign a 2) (out a)) '(() . ())))
;(newline)
;(display (interpret '((assign a 1) (skip) (assign b 2) (assign a (+ a b)) (out a)) '(() . ())))
;(newline)
;(display (interpret '((skip) (assign a 0) (assign b 1) (assign c 2) (if (= a 0) ((out b)) ((out c)))) '(() . ())))
;(newline)
;(display (interpret '((skip) (assign a 3) (assign b 1) (assign c 2) (if (= a 3) ((out b)) ((out c))) (out c))'(() . ())))
;(newline)
(define main
  (display (cdr (interpret primes '(() . ())))))
